package problems.solved;

import java.util.HashMap;
import java.util.Map;

import problems.Problem;

public class Problem92 extends Problem<Integer> {
	private static final int LIMIT = 10000000;
	private static final int CACHE_SIZE = 1000;
	
	public static void main(String[] args) {
		Problem92 problem92 = new Problem92();
		problem92.runTimed();
		problem92.printResult();
	}
	
	@Override
	public void run() {
		int count = 0;
		for (int i = 1; i <= LIMIT; i++) {
			int n = i;
			while (n != 1 && n != 89) {
				n = next(n);
			}
			if (n == 89) {
				count++;
			}
		}
		setResult(count);
	}

	private final Map<Integer, Integer> cache = new HashMap<Integer, Integer>(CACHE_SIZE);
	private int next(int n) {
		if (cache.containsKey(n)) {
			return cache.get(n);
		}
		String string = Integer.toString(n);
		int sum = 0;
		for (int i = 0; i < string.length(); i++) {
			int x = string.charAt(i) - 48;
			sum += x*x;
		}
		if (n < CACHE_SIZE) {
			cache.put(n, sum);
		}
		return sum;
	}
}
